package com.dyz.LeetCodeforSwordFingerOffer;

import java.util.HashMap;

public class CopyRandomList {
    //使用hashMap 存储
//    算法流程：
//    若头节点 head 为空节点，直接返回 null ；
//    初始化： 哈希表 dic ， 节点 cur 指向头节点；
//    复制链表：
//    建立新节点，并向 dic 添加键值对 (原 cur 节点, 新 cur 节点） ；
//            cur 遍历至原链表下一节点；
//            构建新链表的引用指向：
//            构建新节点的 next 和 random 引用指向；
//            cur 遍历至原链表下一节点；
//            返回值： 新链表的头节点 dic[cur] ；
    HashMap<Node,Node> map = new HashMap<>();
     public Node copyRandomList(Node head) {
         if(head==null){
             return null;
         }
         if(map.containsKey(head)){
             return map.get(head);
         }
         Node tmp = new Node(head.val);
         tmp.next = copyRandomList(head.next);
         tmp.random = copyRandomList(head.random);
         return tmp;
    }
}
